/*
* VFS_Group 19 - IIIT-B, MTech Program, 1st Semester, file_name Management.
*
* Implementation of binary Search Tree and all operations on binary search tree.
*
*/

#ifndef STANDARD_IO
#define STANDARD_IO

#include<stdio.h>

#endif

#ifndef STANDARD_LIB
#define STANDARD_LIB

#include<stdlib.h>

#endif

#ifndef STRING_LIB
#define STRING_LIB

#include<string.h>
#include "../include/string_operations.h"

#endif

#include "../include/bst.h"
#include "../include/global_header.h"

// 1. initialize bst

// 2. Insert to bst.

// 3. delete from bst.

// 4. search based on full file path.

// 5. Display (just for testing - implement in-order)

// Global variable which is used to save search result during recursion.
char* search_result;

bst_node_ptr initialize_bst(){

    bst_node_ptr newNode = (bst_node_ptr) malloc(sizeof(bst_node));
	strcpy(newNode->file_path, "root");
	newNode->l_child = NULL;
	newNode->r_child = NULL;

    bst_root = newNode;

    return newNode;
}

void bst_inorder(bst_node_ptr cur){

    if(cur == NULL )
        return;

    bst_inorder(cur->l_child);

    bst_inorder(cur->r_child);
}

void bst_preoder(FILE* fp, bst_node_ptr cur, char* file_path){
    if(cur  == NULL) return;
    int i, count;
        
    char* temp = strrchr(cur->file_path, '/');
	
	count = 0;
    if(temp != NULL && strlen(temp) > 1){
		for(i=0;i<strlen(file_path);i++){
			if(i>(strlen(temp) -1))
				break;
			if(file_path[i] == temp[i+1]) count++;
		}
		
		if(count == strlen(file_path)){
			fprintf(fp, "%s\n", cur->file_path);
		}    	
    }
    /*
    if(strstr(cur->file_path, file_path) != NULL){
        fprintf(fp, "%s\n", cur->file_path);
    }*/

    bst_preoder(fp, cur->l_child, file_path);
    bst_preoder(fp, cur->r_child, file_path);
}

int insert_bst(char* new_filepath){

    bst_node_ptr cur = bst_root;
    bst_node_ptr prev = NULL;

    bst_node_ptr new_node = (bst_node_ptr)malloc(sizeof(bst_node));

    // // printf("new_filepath = %s\n", new_filepath);

    if(new_filepath[strlen(new_filepath) -1] == '/' ){
      //  // printf("Removing /\n");
        strncpy(new_node->file_path, new_filepath,(strlen(new_filepath)-1));
    }
    else{
       // // printf("Not detected \n");
        strcpy(new_node->file_path, new_filepath);
    }

    //// printf("After deleting \ : %s\n", new_node->file_path);
    new_node->l_child = NULL;
    new_node->r_child = NULL;

    while(cur != NULL){
        prev = cur;

        if(cur == NULL){
            return;
        }

        if(strcmp(new_filepath, cur->file_path) > 0){
            cur = cur->r_child;
        }
        else if(strcmp(new_filepath, cur->file_path) < 0){
            cur = cur->l_child;
        }
        else{
           // // printf("Duplicate Node : %s\n", new_filepath);
            return 0;       // Duplicate node detected.
        }
    }

    if(strcmp(new_filepath, prev->file_path) > 0 && (prev->r_child == NULL)){
            prev->r_child = new_node;
    }
    else if(strcmp(new_filepath, prev->file_path) < 0 && (prev->l_child == NULL)){
            prev->l_child = new_node;
    }
    else{
        return -1;      // Cannot insert to BST
    }

    return 1;           // Insertion to BST Success.
}

void bst_search(FILE* fp, char* full_path){

    search_result = (char*)malloc(sizeof(char) * 1024);

    // recursive function writes result to global variable "search_result".
    bst_preoder(fp, bst_root, full_path);
}

bst_node_ptr bst_find_successor(bst_node_ptr node){
    bst_node_ptr prev = NULL;
    bst_node_ptr cur = NULL;

    if(node == NULL)
        return node;

    prev = cur;
    cur = node->r_child;

    while(cur != NULL){
        prev = cur;
        cur = cur->l_child;
    }

    return prev;
}

void bst_delete(char* full_path){

    if(bst_root == NULL){
        return;
    }

    bst_node_ptr cur = bst_root;
    bst_node_ptr prev = NULL;

    while(cur != NULL){

        if(strcmp(full_path, cur->file_path) == 0){
            break;
        }
        else if(strcmp(full_path, cur->file_path) > 0){
            prev = cur;
            cur = cur->r_child;
        }
        else if(strcmp(full_path, cur->file_path) < 0){
            prev = cur;
            cur = cur->l_child;
        }
    }

    if(cur == NULL){
       return; // File/Folder not found.
    }

    // Case 1. Leaf node
    if(cur->r_child == NULL && cur->l_child == NULL){
        //// printf("Entered case 1.\n");
       // // printf("prev->file_path : %s\n", prev->file_path);
            if(prev->l_child == cur)
                prev->l_child = NULL;
            else if (prev->r_child == cur)
                prev->r_child = NULL;
    }
    else if(cur->r_child != NULL || cur->l_child != NULL){ // Case 2: only one child.
        //// printf("Entered case 2.\n");
        if(cur->r_child != NULL){
            if(prev->l_child == cur)
                prev->l_child = cur->r_child;
            else if (prev->r_child == cur)
                prev->r_child = cur->r_child;
        }
        else if(cur->l_child != NULL){
            if(prev->l_child == cur)
                prev->l_child = cur->l_child;
            else if (prev->r_child == cur)
                prev->r_child = cur->l_child;
        }
    }
    else { // Case 3: node to be deleted has 2 child. Find successor and swap.
        //// printf("Entered case 3.\n");
        bst_node_ptr successor = bst_find_successor(cur);

        // swap cur with successor

        successor->l_child = cur->l_child;
        successor->r_child = cur->r_child;

        if(prev->l_child == cur)
             prev->l_child = successor;
        else if (prev->r_child == cur)
            prev->r_child = successor;
    }

    if(cur != NULL) free(cur);

    //// printf("Completed deletion in bst\n");
    bst_inorder(bst_root);
    return;
}
